class Solution {
    /*
        解法1：使用集合，空间复杂度O(N)
    */
    public ListNode middleNode(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while(head!=null){
            list.add(head);
            head = head.next;
        }
        return list.get(list.size()/2);
    }
}
class Solution {
    /*
        解法2：快慢指针
    */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}